{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Partition Labels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #hash-table #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #哈希表 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: partitionLabels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #划分字母区间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。</p>\n",
    "\n",
    "<p>注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 <code>s</code> 。</p>\n",
    "\n",
    "<p>返回一个表示每个字符串片段的长度的列表。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<strong class=\"example\">示例 1：</strong>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ababcbacadefegdehijhklij\"\n",
    "<strong>输出：</strong>[9,7,8]\n",
    "<strong>解释：</strong>\n",
    "划分结果为 \"ababcbaca\"、\"defegde\"、\"hijhklij\" 。\n",
    "每个字母最多出现在一个片段中。\n",
    "像 \"ababcbacadefegde\", \"hijhklij\" 这样的划分是错误的，因为划分的片段数较少。 </pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"eccbbbbdec\"\n",
    "<strong>输出：</strong>[10]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 500</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [partition-labels](https://leetcode.cn/problems/partition-labels/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [partition-labels](https://leetcode.cn/problems/partition-labels/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ababcbacadefegdehijhklij\"', '\"eccbbbbdec\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, s: str) -> List[int]:\n",
    "        ans = []\n",
    "        start = end = 0\n",
    "        for i in range(len(s)):\n",
    "            index = s.rfind(s[i])\n",
    "            if index + 1 > end:\n",
    "                end = index + 1\n",
    "\n",
    "            if end >= len(s):\n",
    "                ans.append(end - start)\n",
    "                return ans\n",
    "\n",
    "            if i >= end - 1:\n",
    "                ans.append(end - start)\n",
    "                start = end\n",
    "        return [len(s)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def partitionLabels(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        lindex = {c: i for i, c in enumerate(S)}\n",
    "        j = anchor = 0\n",
    "        ans = []\n",
    "        for i, c in enumerate(S):\n",
    "            j = max(j, lindex[c])\n",
    "            if i == j:\n",
    "                ans.append(j - anchor + 1)\n",
    "                anchor = j + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        #思路计算每个字母最开始和最后出现的位置，得到一个区间序列，然后按照合并重复区间的方法\n",
    "        #得到合并完成的序列，则每个子序列的长度即为每个字符串片段的长度\n",
    "        data = []\n",
    "        for ch in set(S):\n",
    "            data.append(self.findFirstandLast(ch, S))\n",
    "        return [l[1]-l[0]+1 for l in self.mergeInterval(data)]\n",
    "        \n",
    "    def findFirstandLast(self, ch, S):\n",
    "        start = 0\n",
    "        end = 0\n",
    "        for i in range(len(S)):\n",
    "            if S[i] == ch:\n",
    "                start = i\n",
    "                break\n",
    "        for i in range(len(S)-1,-1,-1):\n",
    "            if S[i] == ch:\n",
    "                end = i\n",
    "                break\n",
    "        return [start, end]\n",
    "        \n",
    "              \n",
    "    def mergeInterval(self, intervals):\n",
    "        intervals = sorted(intervals)\n",
    "        i = 0\n",
    "        while i < len(intervals)-1:\n",
    "            if intervals[i+1][1] <= intervals[i][1]:\n",
    "                intervals.pop(i+1)\n",
    "            elif intervals[i+1][0] <= intervals[i][1]:\n",
    "                intervals[i][1] = intervals[i+1][1]\n",
    "                intervals.pop(i+1)\n",
    "            else:\n",
    "                i+=1\n",
    "        return intervals\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        index_dict = {}\n",
    "        result = []\n",
    "        for i in range(len(S)):\n",
    "            if S[i] in index_dict.keys():\n",
    "                index_dict[S[i]].append(i)\n",
    "            else: index_dict[S[i]] = [i]\n",
    "\n",
    "        index = 0\n",
    "        while index < len(S):\n",
    "            init_range = [index_dict[S[index]][0], index_dict[S[index]][-1]]\n",
    "            i = init_range[0]\n",
    "            while i in range(init_range[0], init_range[-1]):\n",
    "                if index_dict[S[i]][-1] > init_range[-1]: init_range[-1] = index_dict[S[i]][-1]\n",
    "                i += 1\n",
    "            index = init_range[-1] + 1\n",
    "            result.append(init_range[-1] - init_range[0] + 1)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        c_max_index = {}#记录每个字符出现的最大位置\n",
    "        n = len(S)\n",
    "        now_max_index = 0#记录当前扫描的字符串中字符的最大位置\n",
    "        l = 0 #当前扫描字符串的开始位置\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            c_max_index[S[i]] = i\n",
    "        for i in range(n):\n",
    "            now_max_index = max(now_max_index, c_max_index[S[i]])\n",
    "            if i == now_max_index:\n",
    "                res.append(i-l+1)\n",
    "                l = i+1\n",
    "                now_max_index = 0\n",
    "        \n",
    "        return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        vec=[]\n",
    "        for i in range(0,26):\n",
    "            vec.append(0)\n",
    "        last = 0\n",
    "        for i in range(0,len(S)):\n",
    "            vec[ord(S[i])-ord('a')] += 1\n",
    "        st = set()\n",
    "        for i in range(0,len(S)):\n",
    "            st.add(S[i])\n",
    "            vec[ord(S[i])-ord('a')] -= 1\n",
    "            if vec[ord(S[i])-ord('a')]==0:\n",
    "                if S[i] in st:\n",
    "                    st.remove(S[i])\n",
    "                if st==set():\n",
    "                    res.append(i-last+1)\n",
    "                    last=i+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        lastIndexOfChar={}\n",
    "        for i in range(len(S)):\n",
    "            lastIndexOfChar[S[i]]=i\n",
    "        \n",
    "        firstindex=0\n",
    "        partions=[]\n",
    "        while firstindex<len(S):\n",
    "            lastindex = firstindex\n",
    "            i=firstindex\n",
    "            while i<=lastindex:\n",
    "                if lastIndexOfChar[S[i]]>lastindex:\n",
    "                    lastindex = lastIndexOfChar[S[i]]\n",
    "                i+=1\n",
    "            partions.append(lastindex-firstindex+1)\n",
    "            firstindex = lastindex+1\n",
    "        return partions\n",
    "    def char2Index(self,c):\n",
    "        return c-\"a\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: 'str') -> 'List[int]':\n",
    "        i = 0\n",
    "        ans = []\n",
    "        while i < len(S):\n",
    "            j = S.rfind(S[i])\n",
    "            m = j\n",
    "            k = i + 1\n",
    "            while k < m:\n",
    "                m = max(m, S.rfind(S[k]))\n",
    "                k += 1\n",
    "            m += 1\n",
    "            ans.append(m - i)\n",
    "            i = m\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:\n",
    "        dic={}\n",
    "        for i in range(len(S)):\n",
    "            if S[i] not in dic:\n",
    "                dic[S[i]]=[i,i]\n",
    "            else:\n",
    "                dic[S[i]][1]=i\n",
    "        weizhi1=0\n",
    "        weizhi2=dic[S[0]][1]\n",
    "\n",
    "        ans=[]\n",
    "        i=1\n",
    "        while weizhi2<len(S):\n",
    "            while i<=weizhi2:\n",
    "                weizhi2=max(weizhi2,dic[S[i]][1])\n",
    "                i+=1\n",
    "            if weizhi2+1>=len(S):\n",
    "                ans.append(len(S)-weizhi1)\n",
    "                break\n",
    "            else:\n",
    "                ans.append(weizhi2-weizhi1+1)\n",
    "            weizhi1,weizhi2=weizhi2+1,dic[S[weizhi2+1]][1]\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:\n",
    "        dic= {}\n",
    "        for idx, cha in enumerate(S):\n",
    "            dic[cha] = idx\n",
    "        result = []\n",
    "        cur = dic[S[0]]\n",
    "        for i, c in enumerate(S):\n",
    "            if dic[c] > cur:\n",
    "                cur = dic[c]\n",
    "            if i == cur:\n",
    "                result.append(cur+1-sum(result))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:        \n",
    "        last = [-1] * 26        \n",
    "        n = len(S)\n",
    "        nextpos = [-1] * n\n",
    "        for i in range(n)[::-1]:\n",
    "            key = ord(S[i]) - 97\n",
    "            nextpos[i] = last[key]\n",
    "            last[key] = i\n",
    "        \n",
    "        cur = 0\n",
    "        res = []\n",
    "        while cur < n:            \n",
    "            if nextpos[cur] != -1:\n",
    "                right = nextpos[cur]\n",
    "                k = cur\n",
    "                while k <= right:\n",
    "                    right = max(right, nextpos[k])\n",
    "                    k += 1\n",
    "                res.append(right - cur + 1)\n",
    "                cur = right + 1\n",
    "            else:\n",
    "                res.append(1)\n",
    "                cur += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:\n",
    "        #首先找到每个元素出现的最后位置,字典的形式，通过元素找到下标\n",
    "        last={c:i for i,c in enumerate(S)}\n",
    "        #设置区间\n",
    "        start=end=0\n",
    "        #保存字符串的长度\n",
    "        res=[]\n",
    "        #开始遍历元素\"ababcbacadefegdehijhklij\"\n",
    "        for i,c in enumerate(S):\n",
    "            #设置尾部\n",
    "            end=max(end,last[c])\n",
    "            #当区间里所有元素都遍历过\n",
    "            if i==end:          \n",
    "                res.append(end-start+1)\n",
    "                start=i+1\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:\n",
    "        last_index = {c:i for i,c in enumerate(S)}\n",
    "        #统计每一个字母所在的最后位置\n",
    "        #根据index进行分割\n",
    "        j = split = 0\n",
    "        res = []\n",
    "        for i,c in enumerate(S):\n",
    "            j = max(j, last_index[c])\n",
    "            if i == j:\n",
    "                res.append(i - split + 1)\n",
    "                split = i+1\n",
    "            \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:\n",
    "        last = [0] * 26\n",
    "        for i, ch in enumerate(S):\n",
    "            last[ord(ch) - ord(\"a\")] = i\n",
    "        \n",
    "        partition = list()\n",
    "        start = end = 0\n",
    "        for i, ch in enumerate(S):\n",
    "            end = max(end, last[ord(ch) - ord(\"a\")])\n",
    "            if i == end:\n",
    "                partition.append(end - start + 1)\n",
    "                start = end + 1\n",
    "        \n",
    "        return partition\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:\n",
    "        sl = list()\n",
    "        start = 0\n",
    "        for i in range(len(S)):\n",
    "            if set(S[start:i+1]) & set(S[i+1:]):\n",
    "                continue\n",
    "            else:\n",
    "                sl.append(i + 1-start)\n",
    "                start = i + 1\n",
    "        return sl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str):\n",
    "        dic = {s:index for index, s in enumerate(S)}\n",
    "        num = 0\n",
    "        result = []\n",
    "        j = dic[S[0]]\n",
    "        for i in range(len(S)):\n",
    "            num +=1\n",
    "            if dic[S[i]] > j: \n",
    "                j = dic[S[i]]\n",
    "            if i == j:\n",
    "                result.append(num)\n",
    "                num = 0\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:\n",
    "        n = len(S)\n",
    "        ans = []\n",
    "        def traverse(start):\n",
    "            if start > n - 1: return\n",
    "            stack = []\n",
    "            pending = []\n",
    "            for i in range(start, n):\n",
    "                if not stack:\n",
    "                    stack.append(S[i])\n",
    "                    start = i\n",
    "                else:\n",
    "                    if S[i] in stack:\n",
    "                        stack = stack + pending + [S[i]]\n",
    "                        start = i\n",
    "                        pending = []\n",
    "                    else:\n",
    "                        pending.append(S[i])\n",
    "            if stack:\n",
    "                ans.append(len(stack))\n",
    "            traverse(start + 1)\n",
    "        traverse(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:\n",
    "        res = []\n",
    "        char_dict = defaultdict(list)\n",
    "\n",
    "        for index, item in enumerate(S):\n",
    "            char_dict[item].append(index)\n",
    "        def pre(value: str, start):\n",
    "            if not value or start >= len(value):\n",
    "                return\n",
    "            right = 0\n",
    "            right_new = char_dict[value[start]][-1]\n",
    "            temp_start = start\n",
    "            while right_new > right:\n",
    "\n",
    "                right = right_new\n",
    "                char_set = set(value[temp_start:right_new + 1])\n",
    "                temp_start = right_new+1\n",
    "                for c in char_set:\n",
    "                    right_new = max(right_new, char_dict[c][-1])\n",
    "            res.append(right_new+1-start)\n",
    "            pre(S, right_new+1)\n",
    "        pre(S, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:\n",
    "        dic = {}\n",
    "        def calc_len(s):\n",
    "            if s in dic:\n",
    "                return dic[s]\n",
    "            n = len(s)\n",
    "            if n == 1:\n",
    "                return [1]\n",
    "            dp = [False] * n\n",
    "            dp[-1] = True\n",
    "            for i in range(n):\n",
    "                s1 = set(s[:i+1])\n",
    "                s2 = set(s[i+1:])\n",
    "                for w in s1:\n",
    "                    if w in s2:\n",
    "                        dp[i] = True\n",
    "                        break\n",
    "            if all(dp):\n",
    "                dic[s] = [n]\n",
    "                return [n]\n",
    "            ans = 1\n",
    "            res = [n]\n",
    "            for i in range(n):\n",
    "                if not dp[i]:\n",
    "                    left = calc_len(s[:i+1])\n",
    "                    right = calc_len(s[i+1:])\n",
    "                    if len(left) + len(right) > ans:\n",
    "                        ans = len(left) + len(right)\n",
    "                        res = left + right\n",
    "            dic[s] = res\n",
    "            return res\n",
    "        res = calc_len(S)\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, S: str) -> List[int]:\n",
    "        \n",
    "        #思路：贪心法   在处理数组前，统计一遍信息（如频率、个数、第一次出现位置、最后一次出现位置等）\n",
    "        # res = []\n",
    "        # dic = {}\n",
    "        # for index,ch in enumerate(S):  # 返回当前字母和索引\n",
    "        #     dic[ch] = index     #记录该字母最后一次出现的索引值\n",
    "        # #dic = {'a': 8, 'b': 5, 'c': 7, 'd': 14, 'e': 15, 'f': 11, 'g': 13, 'h': 19, 'i': 22, 'j': 23, 'k': 20, 'l': 21}\n",
    "        \n",
    "        # cur = dic[S[0]]     #返回字符串S第一个出现的字母，最后出现的索引值，\n",
    "\n",
    "        # for index,ch in enumerate(S):   #遍历一遍字符串S 返回信息（0，a）（1，b）(2,a).....\n",
    "        #     if dic[ch] > cur:       \n",
    "        #         cur = dic[ch]\n",
    "        #     if index == cur:\n",
    "        #         res.append(cur - sum(res) + 1)\n",
    "        # return res \n",
    "\n",
    "        res = []\n",
    "        dic = {}\n",
    "        for i,c in enumerate(S):\n",
    "            dic[c] = i \n",
    "        start = dic[S[0]]\n",
    "        for i,c in enumerate(S):\n",
    "            if dic[c] > start:\n",
    "                start = dic[c]\n",
    "            if i == start:\n",
    "                res.append(start - sum(res) + 1)\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # last = [0] * 26\n",
    "        # for i,ch in enumerate(S):\n",
    "        #     last[ord(ch) - ord('a')] = i\n",
    "        # partition = list()\n",
    "        # start = end = 0\n",
    "        # for i,ch in enumerate(S):\n",
    "        #     end = max(end,last[ord(ch) - ord('a')])\n",
    "        #     if i == end:\n",
    "        #         partition.append(end - start + 1)\n",
    "        #         start = end + 1\n",
    "        # return partition\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, s: str) -> List[int]:\n",
    "        last = {c:i for i, c in enumerate(s)}\n",
    "        end = start = 0\n",
    "        res =[]\n",
    "        for i, c in enumerate(s):\n",
    "            end = max(end, last[c])\n",
    "            if i == end:\n",
    "                res.append(end - start + 1)\n",
    "                start = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, s: str) -> List[int]:\n",
    "        a = {}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in a:\n",
    "                a[s[i]] = [i,i]\n",
    "            else:\n",
    "                a[s[i]][-1] = i\n",
    "        b = []\n",
    "        for i in a:\n",
    "            b.append(a[i])\n",
    "        \n",
    "        m = 0\n",
    "        n = b[0][1]\n",
    "        res = []\n",
    "        for i in b:\n",
    "            if i[0] <= n and i[1] <= n:\n",
    "                continue\n",
    "            elif i[0] <= n and i[1] > n:\n",
    "                n = i[1]\n",
    "            elif i[0] > n:\n",
    "                res.append(n - m + 1)\n",
    "                m = i[0]\n",
    "                n = i[1]\n",
    "        res.append(n - m + 1)\n",
    "        return res\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, s: str) -> List[int]:\n",
    "        hash_table = [0] * 26\n",
    "        for i in range(len(s)):\n",
    "            hash_table[ord(s[i]) - ord('a')] = i\n",
    "        \n",
    "        results = []\n",
    "        left = 0\n",
    "        right = 0\n",
    "        for i in range(len(s)):\n",
    "            right = max(right, hash_table[ord(s[i]) - ord('a')])\n",
    "            if right == i:\n",
    "                results.append(right - left + 1)\n",
    "                left, right = i+1, i+1\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, s: str) -> List[int]:\n",
    "        res = dict()\n",
    "        f = []\n",
    "        for i in range(len(s)):\n",
    "            res[s[i]] = i\n",
    "        for i in range(len(s)):\n",
    "            f.append(res[s[i]])\n",
    "        index = 0\n",
    "        res = []\n",
    "        print(f)\n",
    "        while index < len(s):\n",
    "            end = f[index]\n",
    "            if end == index:\n",
    "                res.append(1)\n",
    "                index += 1\n",
    "                continue\n",
    "            while max(f[index: end]) != f[end]:\n",
    "                end = max(f[index: end])\n",
    "            res.append(end - index + 1)\n",
    "            index = end + 1\n",
    "        return res\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, s: str) -> List[int]:\n",
    "        # 贪心策略\n",
    "        # 目标是找到最多的不相交子集\n",
    "        # 即 子集1 ∩ 子集2 = ∅\n",
    "        # 所以，当有子母同时出现在多个集合中，可以将其合并\n",
    "\n",
    "        # 预处理\n",
    "        # 提取每个字母开头结尾的索引构成列表\n",
    "        front_end_list =  []\n",
    "        pointer = []\n",
    "        for idx, word in enumerate(s):\n",
    "            all_ = [i for i,x in enumerate(s) if x==word]\n",
    "            if not (idx in pointer):\n",
    "                front_end_list.append([all_[0],all_[-1]])\n",
    "            for j in all_:\n",
    "                pointer.append(j)\n",
    "        \n",
    "        ans = []\n",
    "        set_ = front_end_list[0]\n",
    "        if len(front_end_list) == 1:\n",
    "            ans.append(set_[1] - set_[0] + 1)\n",
    "            return ans\n",
    "\n",
    "        # 从左至右遍历集合\n",
    "        # 如果集合相交则合并，直到找到下一个不相交的集合\n",
    "        for idx in range(1, len(front_end_list)):\n",
    "            # 判断两个集合相交：集合2的开始 <= 集合1的结尾\n",
    "            if front_end_list[idx][0] <= set_[1]:\n",
    "                set_[1] = max(front_end_list[idx][1], set_[1])\n",
    "            # 判断两个集合不相交：集合2的开始 > 集合1的结尾\n",
    "            else:\n",
    "                ans.append(set_[1] - set_[0] + 1)\n",
    "                set_ = front_end_list[idx]\n",
    "            if idx == len(front_end_list) - 1:\n",
    "                ans.append(set_[1] - set_[0] + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, s: str) -> List[int]:\n",
    "        hash = {}\n",
    "        for i in s:\n",
    "            if i not in hash:\n",
    "                hash[i] = s.rfind(i)\n",
    "        result = []\n",
    "        tmp = hash[s[0]]\n",
    "        tmp_str = s[0]\n",
    "        length = 0\n",
    "        for i in range(len(s) - 1):\n",
    "            if i == tmp:\n",
    "                result.append(length + 1)\n",
    "                length = 0\n",
    "                tmp = hash[s[i + 1]]\n",
    "                tmp_str = s[i + 1]\n",
    "            else:\n",
    "                length += 1\n",
    "                if hash[s[i]] > tmp:\n",
    "                    tmp = hash[s[i]]\n",
    "                    tmp_str = s[i]\n",
    "        result.append(length + 1)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, s: str) -> List[int]:\n",
    "        tail_idx=0\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            # 在后面寻找a[i]\n",
    "            if s[i] in s[i+1:]:\n",
    "                tail_idx  = max(s[i+1:].index(s[i])+i +1 , tail_idx)\n",
    "            if i>=tail_idx:\n",
    "                res.append(i)\n",
    "        x = -1\n",
    "        t = []\n",
    "        for num in res:\n",
    "            t.append(num-x)\n",
    "            x = num\n",
    "        if not t:\n",
    "            t.append(len(s))\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionLabels(self, s: str) -> List[int]:\n",
    "\n",
    "        letter_interval = dict()\n",
    "\n",
    "        for index, letter in enumerate(s):\n",
    "            if letter not in letter_interval:\n",
    "                letter_interval[letter] = [index, index]\n",
    "            else:\n",
    "                current_interval = letter_interval[letter]\n",
    "                if len(current_interval)<2:\n",
    "                    letter_interval[letter].append(index)\n",
    "                else:\n",
    "                    letter_interval[letter][1] = index\n",
    "\n",
    "        interval_list = [interval for interval in letter_interval.values()]\n",
    "\n",
    "        n_unique_letters = len(interval_list)\n",
    "\n",
    "        final_res = []\n",
    "        current_interval_len = interval_list[0][1] + 1 \n",
    "        prev_end = interval_list[0][1]\n",
    "        for cur_index in range(1, n_unique_letters):\n",
    "\n",
    "            cur_start = interval_list[cur_index][0]\n",
    "            cur_end = interval_list[cur_index][1]\n",
    "            \n",
    "            if cur_start < prev_end:\n",
    "                if cur_end > prev_end:\n",
    "                    current_interval_len += cur_end - prev_end\n",
    "                    prev_end = cur_end\n",
    "            else:\n",
    "                final_res.append(current_interval_len)\n",
    "                prev_end = cur_end\n",
    "                current_interval_len = cur_end - cur_start + 1\n",
    "        final_res.append(current_interval_len)\n",
    "        return final_res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
